public class demo2 {
    public static void getNext(int[] next,String sub){
        next[0] = -1;
        next[1] = 0;
        int k = 0;
        for (int i = 2; i < sub.length(); i++) {
            if(k == -1 || sub.charAt(i-1) == sub.charAt(k)){
                next[i] = k + 1;
                k ++;
            }else{
                k = next[k];
            }
        }
    }

    public static int KMP(String str, String sub, int post){
        if(str == null || sub == null) return -1;
        int lenStr = str.length();
        int lenSub = sub.length();
        if(lenStr == 0 || lenSub == 0) return -1;
        if(post < 0 || post > lenStr) return -1;

        int i = post;
        int j = 0;

        int[] next = new int[lenSub];
        getNext(next,sub);
        while(i < lenStr && j < lenSub){
            if(j == -1 ||str.charAt(i) == sub.charAt(j)){
                i ++;
                j ++;
            }else{
                j = next[j];
            }
        }
        if(j >= lenSub){
            return i - j;
        }
        return -1;
    }

    public static void main(String[] args) {
        String str = "abcabcda";
        String sub = "cabcda";
        System.out.println(KMP(str,sub,0));
        System.out.println(str.indexOf(sub));
    }
}
